10648. Avengers

 

Nurlashko, Nurbakyt, and Zhora are the last warriors of an ancient ninja clan fighting against the tyranny of Emperor Ren. After a crushing defeat in open battle, they decided to split their army into three camps and switch to guerrilla warfare.

However, the absurd reforms of Emperor Ren imposed strict rules: the roads between cities can only be traveled in one direction. Moreover, the directions were chosen in such a way that it is impossible, after traversing several roads, to return to the original city.

Now the clan is deciding where to place their camps. The emperor's army regularly conducts raids, checking various routes. If, during one such raid, the enemy manages to capture all three camps, the clan will be unable to regroup and will lose the war. Your task is to help choose three cities so that there is no path passing through all of them.

 

Input. The first line contains two integers n, m (1 ≤ n, m ≤ 106) – the number of cities and roads in the empire. The following m lines each contain two integers vi, ui (1 ≤ vi, ui ≤ n), describing a directed road from city vi to city ui.

 

Output. Print three integers – the indices of the cities where the clan should place their camps. If no such triple of cities exists, print −1. If there are multiple solutions, you may output any of them.

 

Sample input 1

Sample output 1

3 2

1 2

2 3

-1

 

 

Sample input 2

Sample output 2

3 2

1 2

1 3

2 3 1

 

 

SOLUTION

graphs - topological sort

 

Algorithm analysis

The task is to find any three vertices in the graph that are not located on a single path.

To do this, we run Kahn’s topological sorting algorithm. We look for two vertices that appear in the queue at the same time. In this situation, there is no path that passes through both of these vertices. By adding any third vertex to them, we obtain the desired solution.

If, during the execution of Kahn’s algorithm, the queue never contains more than one vertex at a time, this means that all vertices in the graph lie on a single path.

 

Example

The graphs from the sample tests have the following structure:

·        In the first example, all three vertices lie on a single path.

·        In the second example, there exist three vertices that do not lie on a single path.

 

Algorithm implementation

Declare the data structures. The input graph is represented by the adjacency list g, and the in-degrees of the vertices are stored in the array InDegree.

 

vector<vector<int> > g;

vector<int> InDegree;

deque<int> q;

 

Read the input data.

 

scanf("%d %d", &n, &m);

g.resize(n + 1);

InDegree.resize(n + 1);

for (i = 0; i < m; i++)

{

  scanf("%d %d", &a, &b);

  g[a].push_back(b);

 

For each edge (a, b), increment InDegree[b] by 1.

 

  InDegree[b]++;

}

 

All vertices with an in-degree of zero are added to the queue q.

 

for (i = 1; i < InDegree.size(); i++)

  if (InDegree[i] == 0) q.push_back(i);

 

The three desired vertices are stored in the variables x, y and z.

 

x = y = -1;

 

Continue executing the algorithm as long as the queue q is not empty.

 

while (!q.empty())

{

 

If the queue contains more than one vertex at the same time, this means that the solution has been found.

 

  if (q.size() > 1)

  {

    x = q[0];

    y = q[1];

    break;

  }

 

Extract the vertex v from the queue – it will become the current vertex in the topological order.

 

  v = q.front(); q.pop_front();

 

Remove from the graph all edges of the form (v, to). For each such edge, decrease the in-degree of the vertex to. If the in-degree of to becomes zero, add it to the queue.

 

  for (int to : g[v])

  {

    InDegree[to]--;

    if (InDegree[to] == 0) q.push_back(to);

  }

}

 

Kahn’s algorithm is complete. If the value of x is still -1, this means that no solution exists.

 

if (x == -1)

  printf("-1\n");

else

{

 

If a solution exists, choose z as the smallest vertex different from x and y.

 

  z = 1;

  while (z == x || z == y) z++;

    printf("%d %d %d\n", x, y, z);

}